package com.lee.algorithm.sort;

/***
 * @description: 冒泡排序
 *      相邻元素比较，小的往上冒，大的往下沉
 * @author : 青石路
 * @date: 2021/11/22 9:32
 */
public class BubbleSort {

    public static void main(String[] args) {
        int[] arr = new int[]{1,0,4,3,2,9,7};
        bubbleSort2(arr);
        SortUtil.print(arr);
    }

    /**
     * 相邻元素比较，大的往下沉
     * @param arr
     */
    public static void bubbleSort(int[] arr) {

        if (arr == null || arr.length < 2) {
            return;
        }

        // i ~ n-1 已有序，处理 0 ~ i
        for (int i=arr.length-1; i>=0; i--) {

            // 0 ~ i，大的往下沉
            for (int j=0; j<i; j++) {
                if (arr[j] > arr[j+1]) {
                    SortUtil.swap(arr, j, j+1);
                }
            }
        }
    }

    /**
     * 相邻元素比较，小的往上冒
     * @param arr
     */
    public static void bubbleSort2(int[] arr) {

        if (arr == null || arr.length < 2) {
            return;
        }

        // 0 ~ i-1 已有序，处理 i ~ n-1
        for (int i=1; i<arr.length; i++) {

            // 0 ~ i，小的往上冒
            for (int j=arr.length-1; j>=i; j--) {
                if (arr[j] < arr[j-1]) {
                    SortUtil.swap(arr, j, j-1);
                }
            }
        }
    }
}
